package leetcode.code1048;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import leetcode.helper.H;

public class Solution {
	public int longestStrChain(String[] words) {
		Arrays.sort(words, (a, b) -> a.length() - b.length());
		Map<String, Integer> map = new HashMap<>();//
		map.put("", 0);
		int ans = 0;
		for (String word : words) {
			char[] cs = word.toCharArray();
			int cur = Math.max(1, map.getOrDefault(words, 0));
			for (int i = 0; i < cs.length; i++) {
				String tmp = new String(cs, 0, Math.max(0, i))
						+ new String(cs, Math.min(cs.length, i + 1), Math.max(0, cs.length - i - 1));
				cur = Math.max(cur, map.getOrDefault(tmp, 0));
				if (map.containsKey(tmp)) {
					cur = Math.max(cur, map.get(tmp) + 1);
				}
			}
			map.put(word, cur);
			ans = Math.max(ans, cur);
		}
		return ans;
	}

	public static void main(String[] args) {
		char[] cs = "hello".toCharArray();
//		System.out.println(new String(cs, 6, 0));
		Solution so = new Solution();
		int ans1 = so.longestStrChain(H.str2array2("[\"a\",\"b\",\"ba\",\"bca\",\"bda\",\"bdca\"]"));
		System.out.println(ans1);
		int ans = so.longestStrChain(H.str2array2("[\"xbc\",\"pcxbcf\",\"xb\",\"cxbc\",\"pcxbc\"]"));
		System.out.println(ans);
	}
	
	
}
